package matrix;

import org.junit.Test;

/**
 * @author kunkun
 * @className matrix.LeetCode_240
 * @Description ...
 * @date 2025/3/12 14:01
 */
public class LeetCode_240 {

    public boolean searchMatrix(int[][] matrix, int target) {
        return solution3(matrix,target);
    }

    @Test
    public void test(){
        //[],[],[],[],[]
        int[] num1 = {1, 4, 7, 11, 15};
        int[] num2 = {2,5,8,12,19};
        int[] num3 = {3,6,9,16,22};
        int[] num4 = {10,13,14,17,24};
        int[] num5 = {18,21,23,26,30};

        int[][] nums = {num1, num2, num3, num4, num5};

        System.out.println(searchMatrix(nums, 5));
    }




    /**
    * @Description: 方法1：直接查找
    * @Author: kunkun
    * @Date:  2025/3/12 14:12
    * @Parameters:
    * @Return
    * @Throws
    */
    private boolean solution_1(int[][] matrix, int target) {

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }

    /**
    * @Description: 方法2：每行二分
    * @Author: kunkun
    * @Date:  2025/3/12 14:12
    * @Parameters:
    * @Return
    * @Throws
    */
    private boolean solution_2(int[][] matrix, int target) {

        for (int i = 0; i < matrix.length; i++) {
            if (midSearch_2(matrix[i],target,0,matrix[i].length-1)){
                return true;
            }
        }
        return false;
    }

    //二分查找--递归
    public boolean midSearch_1(int[] nums,int target,int start,int end){
        if (start>end){
            return false;
        }
        if (start==end){
            return nums[start]==target;
        }
        int mid = (start+end)/2;
        boolean flag1 = midSearch_1(nums, target, start, mid);
        boolean flag2 = midSearch_1(nums, target, mid+1, end);
        return flag1||flag2;
    }

    //二分查找--普通
    public boolean midSearch_2(int[] nums,int target,int start,int end){
        while (start<=end){
            int mid = (start+end)/2;
            if (nums[mid]==target){
                return true;
            } else if (nums[mid]<target) {
                start=mid+1;
            }else {
                end=mid-1;
            }
        }
        return false;
    }

    private boolean solution3(int[][] matrix, int target){
        //1. 从右上角开始判断
        int i=0,j=matrix[0].length-1;
        while(i< matrix.length && j>=0){
            //2. 条件判断
            if (matrix[i][j]>target){
                j--;
            } else if (matrix[i][j]<target) {
                i++;
            }else {
                return true;
            }
        }
        return false;
    }

}
